#pragma once
#include <iostream>
using namespace std;

template <class T>
struct Node
{
	Node(const T& x = T())
		:_next(nullptr)
		, _data(x)
	{}
	Node* _next;
	T _data;
};

template <class T>
class list
{
	typedef Node<T> Node;
public:
	list()
		:_size(0)
	{
		_head = new Node();
		_head->_data = 0;
		_head->_next = nullptr;
	}
	~list()
	{
		Node* cur = _head->_next;
		while (cur != nullptr)
		{
			Node* next = cur->_next;
			delete cur;
			cur = next;
		}
		_head = nullptr;
	}
	void Print()
	{
		Node* cur = _head->_next;
		while (cur)
		{
			cout << cur->_data << " ";
			cur = cur->_next;
		}
		cout << endl;
	}
	void insert(size_t pos, const T& x)
	{
		Node* cur = _head;
		while (pos--)
		{
			cur = cur->_next;
		}
		Node* next = cur->_next;
		Node* newnode = new Node(x);

		//   newnode
		// cur    next
		cur->_next = newnode;
		newnode->_next = next;

		_size++;
	}
	void erase(size_t pos)
	{
		Node* cur = _head->_next;
		Node* prev = _head;
		while (pos--)
		{
			prev = cur;
			cur = cur->_next;
		}
		Node* next = cur->_next;

		// prev cur next
		prev->_next = next;
		delete cur;
		cur = nullptr;

		_size--;
	}
	void push_back(const T& x)
	{
		insert(_size, x);
	}
	void pop_back()
	{
		erase(_size - 1);
	}
	void push_front(const T& x)
	{
		insert(0, x);
	}
	void pop_front()
	{
		erase(0);
	}
private:
	Node* _head;
	size_t _size;
};

